#include <stdio.h>   // 提供 printf、fgets 等标准输入输出函数
#include <string.h>  // 提供字符串处理函数，如 strtok、strcspn
#include <stdlib.h>  // 提供动态内存分配函数 malloc 和 atoi 字符串转整型
#include <ctype.h>   // 提供字符判断函数，如 isdigit、isspace

#define MAX_QUEUE 100  // 定义最大输入长度

// step 1# 检查字符串中是否包含非法字符（非数字或空格）
int isInvalid(const char *str) {
    while (*str) {
        if (!isdigit(*str) && !isspace(*str)) {
            return 1;  // 有非法字符
        }
        str++;
    }
    return 0;  // 字符串合法
}

int main() {
    // step 2# 为输入字符串和整数数组动态分配内存
    char *input = (char *)malloc(sizeof(char) * MAX_QUEUE);  // 存储原始输入
    int *arr = (int *)malloc(sizeof(int) * MAX_QUEUE);       // 存储转换后的整数
    int arrNum = 0;  // 当前输入的整数个数

    // step 3# 获取用户输入并去除结尾换行符
    fgets(input, sizeof(char) * MAX_QUEUE, stdin);              // 从标准输入读取字符串
    input[strcspn(input, "\n")] = 0;                             // 用 '\0' 替换换行符

    // step 4# 若输入非法（含非数字和空格字符），输出空数组并退出
    if (isInvalid(input)) {
        printf("[]\n");  // 非法输入提示
        return 0;
    }

    // step 5# 使用 strtok 分割字符串，并使用 atoi 转换为整数存入 arr 数组
    char *token = strtok(input, " ");      // 分割第一个数字
    while (token != NULL) {
        arr[arrNum++] = atoi(token);       // 转换并存储当前数字
        token = strtok(NULL, " ");         // 获取下一个数字
    }

    // step 6# 遍历数组进行相邻元素的“高矮交替”调整，尽可能减少移动距离
    for(int i = 0; i < arrNum - 1; i++) {
        if (i % 2 == 0) {  // 偶数位应该是高个子
            if (arr[i] < arr[i + 1]) {
                int tmp = arr[i + 1];      // 交换两个元素
                arr[i + 1] = arr[i];
                arr[i] = tmp;
            }
        }
        else {  // 奇数位应该是矮个子
            if (arr[i] > arr[i + 1]) {
                int tmp = arr[i + 1];
                arr[i + 1] = arr[i];
                arr[i] = tmp;
            }
        }
    }

    // step 7# 输出调整后的身高序列
    for(int i = 0; i < arrNum; i++) {
        printf("%d ", arr[i]);  // 输出数组中每个小朋友的身高
    }

    return 0;
}
